class Solution(object):
    def sortTransformedArray(self, nums, a, b, c):
        """
        :type nums: List[int]
        :type a: int
        :type b: int
        :type c: int
        :rtype: List[int]
        """
        n = len(nums)
        out = [0] * n
        if a == 0:
            for i in range(n):
                out[i] = b * nums[i] + c
            if b >= 0:
                return out
            else:
                out.reverse()
                return out
        x = - b / (2 * a)
        mid_left = 0
        mid_right = 0
        while mid_right < n:
            if nums[mid_right] >= x:
                mid_left = mid_right - 1
                break
            else:
                mid_left = mid_right
                mid_right += 1
        for i in range(n):
            if mid_left >= 0 and mid_right < n:
                if (nums[mid_right] - x) >= (x - nums[mid_left]):
                    out[i] = a * nums[mid_left] ** 2 + b * nums[mid_left] + c
                    mid_left -= 1
                else:
                    out[i] = a * nums[mid_right] ** 2 + b * nums[mid_right] + c
                    mid_right += 1
            else:
                if mid_left >= 0:
                    out[i] = a * nums[mid_left] ** 2 + b * nums[mid_left] + c
                    mid_left -= 1
                else:
                    out[i] = a * nums[mid_right] ** 2 + b * nums[mid_right] + c
                    mid_right += 1
        if a > 0:
            return out
        else:
            out.reverse()
            return out


data = Solution()
nums = [-4,-2,2,4]
a = 0
b = -3
c = 5
print(data.sortTransformedArray(nums, a, b, c))
